class Solution {
public:
    ListNode* getMid(ListNode* head) {
        if (head == nullptr)
            return NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        // 要找到中间节点很简单，快指针一次走两步，慢指针一次走一步
        // 当快指针指向空（节点数量为奇数）或快指针的next为NULL（节点数量为偶数）
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    } // 这个函数的目的是找到回文链表的中间点往后的那个节点
    ListNode* reverseList(ListNode* head) {
        // 首先是递归的出口
        if (head == nullptr || head->next == nullptr) {
            return head;
        } // 如果只有一个节点了/没有节点了直接返回即可
        // 然后我们要相信re这个函数能够帮助我们完成head后面所有节点的逆置，并且最后会返回新的头节点
        ListNode* newhead = reverseList(head->next);
        // 然后我们逆置我们当前的这个节点即可
        head->next->next = head;
        head->next = nullptr; // 让这最后一个节点指向nullptr
        return newhead;
    } // 这个函数的目的是翻转cur后面的点
    bool isPalindrome(ListNode* head) {
        // 首先是找到中间的节点
        // 然后是翻转中间节点往后的节点，然后从
        // 中间节点往后的一个节点开始，和head节点进行值判断
        // 如果值不相等代表不是一个回文链表。否则就是一个回文链表
        ListNode* mid = getMid(head);
        cout<<mid->val<<endl;
        ListNode* cur2 =
            reverseList(mid); // 翻转后面的链表,同时获取翻转后的头节点
        ListNode* cur1 = head;
        while (cur2) {
            if (cur1->val != cur2->val) {
                return false; // 说明不是一个回文链表
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        // 不存在不相同的点
        return true;
    }
};